package com.cat.math;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/
 * @create 2025/10/17 20:03
 * @since JDK17
 */

public class Solution18 {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        long ans = 0;
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Long> h = new HashMap<>();
        for (int x : nums1) {
            map.merge(x, 1, Integer::sum);
            max = Math.max(max, x);
        }

        for (int num : nums2) {
            int x = num * k;
            if (h.containsKey(x)) {    // 不包含
                ans += h.get(x);
                continue;
            }
            long cnt = 0;
            for (int y = x; y <= max; y += x) {
                cnt += map.getOrDefault(y, 0);
            }
            h.put(x, cnt);
        }

        return ans;
    }
}
